package com.itheima.algorithm.datastructure;

public class Leetcode19 {

    public ListNode removeNthFormEnd(ListNode head,int n){
        ListNode s = new ListNode(-1,head);
        recursion(s, n);
        return head;
    }

    /**
     * 递归
     * @param p
     * @param n
     * @return
     */
    public int recursion(ListNode p,int n){
        if(p == null){
            //如果倒着数,算第0个
            return 0;
        }
        // 下一个节点的倒数位置
        int nth = recursion(p.next, n);
        System.out.println(p.value +""+nth);
        // 当前节点倒数位置

        if(nth ==n){
            // p=3 p.next.next = 5
            p.next = p.next.next;
        }
        return nth+1;

    }

    /**
     * 快慢指针法
     * @param head
     * @param n 倒数x
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head,int n){
        ListNode s= new ListNode(-1,head);
        ListNode p1 =s;
        ListNode p2 =s;
        for (int i = 0; i < n+1; i++) {
            p2 = p2.next;
        }
        while (p2!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return s.next;

    }


    public static void main(String[] args) {

    }
}
